Minimum Window Subsequence

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 76 ms)

Metric	Value
Runtime	76 ms
Memory	39.9 MB
Date	2022-01-24

Solution

public class Solution {
    public string MinWindow(string s1, string s2) {
        int m = s1.Length;
    int n = s2.Length;
    int start = 0, len = Int32.MaxValue,  count=0;
    for (int i = 0; i < m; i++)
    {
        if(s1[i]==s2[count]) count++;
        if(count == n)
        {
            int d = i;
            while(count>0)
            {
                if(s2[count-1] == s1[d])
                {
                    count--;
                }
                d--;
            }
            
            if(i-d < len)
            {
                len = i-d;
                start = d+1;
            }
            i=d+1;
        }
    }
    if(len == Int32.MaxValue) return "";
    return s1.Substring(start, len);
    }
}

📜 2 more C# submission(s)

Submission (2022-01-24) — 84 ms, 39.6 MB

public class Solution {
    public string MinWindow(string s1, string s2) {
        int m = s1.Length;
    int n = s2.Length;
    int start = 0, len = Int32.MaxValue, count = 0;
    for (int i = 0; i < m; i++)
    {
        if (s1[i] == s2[count]) count++;
        if (count == n)
        {
            int j = i;
            while (count > 0)
            {
                if (s2[count - 1] == s1[j--])
                {
                    count--;
                }
            }
            j++; // index in s1 which is the first character in s2

            if (len > i - j + 1)
            {
                len = i - j + 1;
                start = j;
            }
            // move back i so it starts next search from j+1 in next iteration
            i = j;
        }
    }
    if (len == Int32.MaxValue) return "";
    return s1.Substring(start, len);
    }
}

Submission (2022-01-24) — 166 ms, 36.8 MB

public class Solution {
    public string MinWindow(string s1, string s2) {
        int m = s1.Length;
    int n = s2.Length;
    int start = 0, len = Int32.MaxValue, count = 0;
    for (int i = 0; i < m; i++)
    {
        if (s1[i] == s2[count]) count++;
        if (count == n)
        {
            int j = i;
            while (count > 0)
            {
                if (s2[count - 1] == s1[j])
                {
                    count--;
                }
                j--;
            }
            j++; // index of the first character in s2
            
            if(len>i-j+1)
            {
            len = i-j+1;
                start = j;
            }
            i = j;
        }
    }
    if (len == Int32.MaxValue) return "";
    return s1.Substring(start, len);
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed